#include <stdio.h>

struct Node {
  Node(int val) : data(val), left(NULL), right(NULL) { }
  int data;
  Node *left, *right;
};

void BTreeToList(Node *root, Node **head, Node **tail) {
  *head = *tail = NULL;

  if (root == NULL) return;

  Node *lh, *lt;
  BTreeToList(root->left, &lh, &lt);

  Node *rh, *rt;
  BTreeToList(root->right, &rh, &rt);

  root->left = root->right = NULL;
  *head = *tail = root;

  if (NULL != lh) {
    lt->right = *head;
    (*head)->left = lt;
    *head = lh;
  }

  if (NULL != rh) {
    (*tail)->right = rh;
    rh->left = *tail;
    *tail = rt;
  }
}

void AddNode(Node **root, int data) {
  if (NULL == *root) {
    *root = new Node(data);
  }
  else if (data > (*root)->data) {
    AddNode(&(*root)->right, data);
  }
  else {
    AddNode(&(*root)->left, data);
  }
}

void BuildTree(Node **root, int data[], int n) {
  *root = NULL;
  for (int i = 0; i < n; ++i) {
    AddNode(root, data[i]);
  }
}

void DeleteTree(Node *root) {
  if (NULL == root) return;

  DeleteTree(root->left); 
  DeleteTree(root->right);

  delete root;
}

void DeleteList(Node *head) {
  for (Node *p = head; p != NULL; p = head) {
    head = p->right;
    delete p;
    p = NULL;
  }
}

void PrintList(Node *head) {
  for (Node *p = head; p != NULL; p = p->right) {
    printf("%d, ", p->data);
  }
  printf("\n");
}

void PrintListRev(Node *tail) {
  for (Node *p = tail; p != NULL; p = p->left) {
    printf("%d, ", p->data);
  }
  printf("\n");
}

void PrintTree(Node *root) {
  if (NULL == root) return;

  PrintTree(root->left);
  printf("%d, ", root->data);
  PrintTree(root->right);
}

int main() {
  int data[] = { 10, 4, 8, 12, 16, 6, 14 };
  Node *root;
  BuildTree(&root, data, 7);
  PrintTree(root);
  printf("\n");

  Node *head, *tail;
  BTreeToList(root, &head, &tail);
  PrintList(head);
  PrintListRev(tail);

  DeleteList(head);
}
